package com.hsc.sort;

/**
 * @author
 * @date 2025-04-25
 * @Description 插入排序 将待排序的元素插入已经排好序的序列中的正确位置，直到整个序列有序。
 */
public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {5, 2, 4, 6, 1, 3, 12, 88, 2};
        System.out.println("排序前：");
        printArray(arr);

        insertionSort3(arr);

        System.out.println("排序后：");
        printArray(arr);
    }


    /**
     * 实现方式一：插入排序
     *
     * @param arr
     */
    public static void insertionSort(int[] arr) {
        // [1, 1，5，6， 8, 9，10，12，13, 20】
        // 数组元素 用来控制轮次
        int n = arr.length;
        // 遍历数组元素，从第二个元素开始，所以 i=1 不是i=0开始
        // 依次与前面的元素比较和交换
        for (int i = 1; i < n; i++) {
            // 当前元素下标 抓取一张牌
            int current = i;
            // 将牌插入 排好的牌中
            // current ：当前元素 我们从1 开始 因为从0开始没有意义
            // 第一步：current - 1 ：表示当前元素的前一个元素的下标大于 0 最小的位置 1-1 =0 是数组 最小下标的位置 必须满足该条件
            // 第二步：比较交arr[current] < arr[current]当前元素比前元素 arr[current - 1]小 就进行交换 相当于摸了一张牌之后 如果摸到的牌比拿在手中的牌小 就把牌插入到排好序的牌中
            while (current - 1 >= 0 && arr[current] < arr[current - 1]) {
                // 第三步：交换元素 如果当前的元素 小于前面的元素，则交换位置
                int temp = arr[current];
                arr[current] = arr[current - 1];
                arr[current - 1] = temp;
                // 第四步：递减 也是要挨个的比较 当前的元素满足上面的条件 做了元素的交换 继续往前比较交换
                current--;
            }
        }
    }

    // 辅助方法：打印数组
    private static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }


    /**
     * 优化代码：插入排序
     * 场景：
     * 摸牌 然后插入牌中
     *
     * @param arr
     */
    public static void insertionSort2(int[] arr) {
        // [1, 1，5，6， 8, 9，10，12，13, 20】
        // 数组元素 用来控制轮次
        int n = arr.length;
        // 遍历数组元素，从第二个元素开始，所以 i=1 不是i=0开始
        // 依次与前面的元素比较和交换
        for (int curr = 1; curr < n; curr++) {
            // 当前元素下标
            // 1、int pre=curr-1 表示当前位置的前一个位置 curr 从 1开始
            // pre >= 0 :表示前一个元素起码大于 0 数组最小的位置为索引为0
            // arr[pre]：前一个位置的的值
            //  arr[pre + 1]:当前位置值
            // arr[pre] > arr[pre + 1]: 当前位置比前一个位置小
            for (int pre = curr - 1; pre >= 0 && arr[pre] > arr[pre + 1]; pre--) {
                // 2、
                // arr[pre] 当前位置的前一个位置
                // arr[pre+1] 当前位置
                // 如果当前的元素 小于前面的元素，则交换位置
                int temp = arr[pre];
                arr[pre] = arr[pre + 1];
                arr[pre + 1] = temp;
                //3、 pre-- 继续向前比较交换
            }

        }
    }

    /**
     * 插入排序方法三
     *
     * @param array
     */
    public static void insertionSort3(int[] array) {

        //1、想象摸牌 2、再插入有序的牌中
        // 从数组中的第1个元素作为摸牌的第一张
        // 为何要从第一个元素开始  至少需要一个元素进行比较
        // 第0个元素 只有一个 默认有序
        // 在一个元素数组中 每次摸取一个元素 所有需要循环进行获取
        for (int i = 1; i < array.length; i++) {
            // 每次循环 就是从队列中抓取一个元素 i的位置进行递增
            // 下面就是比较的过程
            // 当前元素从i=1 开始 i 逐步递增 挨个拿元素进行比较
            // 当前元素与前面的数组元素挨个相比
            // 假设数组元素为  [5, 2，1，6， 8, 9，10，12，13, 20】
            // i=1 时 元素为 2  进行比较 2 < 5 所以进行元素的交换 变成了[2, 5，1， 8, 9，10，12，13, 20】
            // i=2 是 元素为1  此时 需要比较的数组元素为 [2,5] 我们需要已经对前面排好序的挨个比较 1 与5 比较 1小于5 进行交换 得到元素数组为[2, 1，5， 8, 9，10，12，13, 20】
            // 此时 比完之后 1的位置来到了i=1的位置 1 需要继续跟 2 比较 1 <2 进行交换 得到数组为 [1, 2，5， 8, 9，10，12，13, 20]
            // 这里我们需要考虑的问题就是 每次拿到的当前元素 不单单只要比一次 需要比多次 而且的下标 是逐步递减 的因为需要跟前面的元素数组进行挨个比较 就像是 我们摸了一张牌  跟手中的牌的一个个比完之后
            // 才进行插入
            // 所以我们 要比较的元素就从 i-1 开始 ,j的最终的位置一定是大于0的 因为j的位置会前面的比较 逐步递减 总不能小于0 吧 就会数组越界了
            // int j=i-1 的含义 我们从i=1 开始的 我们需要从数组元素最开始比较 所有j=i-1 表示 j=0 从数组元素最开始的位置进行比较
            for (int j = i - 1; j >= 0; j--) {
                // 进行比较交换 如果当前元素比前一个小 就交换
                // [5, 2，1，6， 8, 9，10，12，13, 20】
                // j+1 表示的含义：因为上面的j-1 开始的 ，表示当前元素的一下一个数组元素位置 举例 当前我们的元素是 i=1 也就是元素2 所以当前的元素从j=1 开始进行比较
                // [j+1]=2
                // [j]=5
                if (array[j + 1] < array[j]) {
                    // 交换元素
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
                // 结束一次比较之后 进行元素下标递减进行 比较 所以是 j--
            }


        }


    }
}